package linkedList;

// 无头双向链表实现
public class MyDLinkedList {
    static class Node{
        private String val;
        private Node prev = null;
        private Node next = null;

        public Node(){
            this("");
        }
        public Node(String val) {
            this.val = val;
        }
    }

    //链表的头，表示整个链表
    private Node head = null;
    //链表的尾，便于尾插
    private Node tail = null;

    //头插法
    public void addFirst(String data){
        Node newNode = new Node(data);
        //空链表
        if(head == null){
            head = newNode;
            tail = newNode;
        }else{//非空链表
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }
    //尾插法
    public void addLast(String data){
        Node newNode = new Node(data);
        //空链表
        if(head == null){
            head = newNode;
            tail = newNode;
        }else{  //非空链表
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index, String data){
        //检查下标是否合法，不合法返回false
        if(index < 0 || index > size()){
            return false;
            //throw new RuntimeException("下标超出范围，index:" + index + ", size:" + size());
        }
        //头插
        if(index == 0){
            addFirst(data);
            return true;
        }
        //尾插
        if(index == size()){
            addLast(data);
            return true;
        }

        Node cur = head;
        //找到要插入的位置
        for(int i = 0; i < index; i++){
            cur = cur.next;
        }
        //插入位置的前一个位置
        Node prev = cur.prev;
        //创建要插入的新结点
        Node newNode = new Node(data);

        newNode.next = cur;
        newNode.prev = prev;

        prev.next = newNode;
        cur.prev = newNode;

        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(String key){
        //遍历链表
        for(Node cur = head; cur != null; cur = cur.next){
            //找到包含key的结点，返回true
            if(cur.val.equals(key)){
                return true;
            }
        }
        //遍历完链表，未找到，返回false
        return false;
    }
    // 查找元素, 返回该元素的下标. 如果没找到, 返回 -1.
    public int indexOf(String key){
        int ret = -1, i = 0;
        for(Node cur  = head; cur != null; cur = cur.next){
            if(cur.val.equals(key)){
                ret = i;
                break;
            }
            i++;
        }
        return ret;
    }
    //删除第一次出现关键字为key的节点
    public boolean remove(String key){
        //空链表，删除失败，返回false
        if(head == null){
            return false;
        }

        //检查头结点是否是要删除的结点
        if(head.val == key){
            //头尾相等，即链表只有一个结点，将头尾置空
            if(head == tail){
                head = tail = null;
            }else{  //不相等，更新头
                head = head.next;
            }
            return true;
        }
        //从头结点的后一个结点开始查找
        for(Node cur = head.next; cur != null; cur = cur.next){
            //找到了第一个与key相等的结点的值
            if(cur.val.equals(key)){
                //检查此节点是否尾结点
                if(cur == tail){
                    //是尾结点，更新tail指向尾结点的上一节点，并将上一节点的next置空
                    tail = tail.prev;
                    tail.next = null;
                }else{
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                return true;
            }
        }
        return false;
    }
    //删除所有值为key的节点
    public boolean removeAllKey(String key){
        if(head == null){
            return false;
        }
        boolean flag = false;
        //从第二个结点开始查找要删除的结点，找到并删除
        for(Node cur = head.next; cur != null; cur = cur.next){
            if(cur.val.equals(key)){
                //注意要删除的结点是否尾结点
                if(cur == tail){
                    tail = tail.prev;
                    tail.next = null;
                }else{
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                flag = true;
            }
        }
        //检查头结点是否需要删除
        if(head.val == key){
            //注意链表只有一个结点的情况
            if(head == tail){
                head = tail = null;
            }else{
                head = head.next;
            }
            flag = true;
        }

        return flag;
    }
    //得到单链表的长度
    public int size(){
        int size = 0;
        for(Node cur = head; cur != null; cur = cur.next){
            size++;
        }
        return size;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for(Node cur = head; cur != null; cur = cur.next){
            stringBuilder.append(cur.val);
            if(cur.next != null){
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    public void clear(){
        head = null;
        tail = null;
    }


    public static void main(String[] args) {
        MyDLinkedList list = new MyDLinkedList();
        for(int i = 0; i < 10; i++){
            list.addLast("" + (char)('a' + i));
        }
        System.out.println(list);

        list.addIndex(0, "wang");
        System.out.print("list.addIndex(0, \"wang\")           ");
        System.out.println(list);
        list.addIndex(list.size(), "wang");
        System.out.print("list.addIndex(list.size(), \"wang\") ");
        System.out.println(list);
        list.addIndex(6, "wang");
        System.out.print("list.addIndex(6, \"wang\")           ");
        System.out.println(list);

        list.remove("c");
        System.out.println(list);
        list.remove("wang");
        System.out.println(list);
        list.removeAllKey("wang");
        System.out.println(list);
        list.remove("j");
        System.out.println(list);
        System.out.println(list.size());
        System.out.println(list.contains("f"));
        System.out.println(list.contains("wang"));
        System.out.println(list);
        System.out.println(list.indexOf("e"));
        System.out.println(list.indexOf("wang"));
        list.clear();
        System.out.println(list);
    }
}
